//1557. 可以到达所有点的最少点数目

//给你一个 有向无环图 ， n 个节点编号为 0 到 n - 1 ，以及一个边数组 edges ，其中 edges[i] = [fromi, toi] 表示一条从点  fromi 到点 toi 的有向边。
//找到最小的点集使得从这些点出发能到达图中所有点。题目保证解存在且唯一。
//你可以以任意顺序返回这些节点编号。

//class Solution {
//public:
//    vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
//        vector<int> cnt(n);
//        for (const auto& edge : edges) {
//            cnt[edge[1]]++;
//        }
//
//        vector<int> ans;
//        for (int i = 0; i < n; i++) {
//            if (cnt[i] == 0) {
//                ans.emplace_back(i);
//            }
//        }
//
//        return ans;
//    }
//};

//210. 课程表 II

//现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
//例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0, 1] 。
//返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

//class Solution {
//public:
//    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
//        vector<vector<int>> edges(numCourses);
//        for (const auto& p : prerequisites) {
//            edges[p[1]].emplace_back(p[0]);
//        }
//        bool valid = true; // 判断有向图中是否有环
//        vector<int8_t> vis(numCourses);
//        vector<int> ans;
//        auto dfs = [&](this auto&& dfs, int u) -> void {
//            vis[u] = 1;
//            for (auto& e : edges[u]) {
//                if (!vis[e]) {
//                    dfs(e);
//                    if (!valid) {
//                        return;
//                    }
//                }
//                else if (vis[e] == 1) { // 如果找到了环
//                    valid = false;
//                    return;
//                }
//            }
//            vis[u] = 2; // 将节点标记为已完成
//            ans.emplace_back(u);
//            };
//        // 每次挑选一个未搜索的节点，开始进行深度优先搜索
//        for (int i = 0; i < numCourses && valid; ++i) {
//            if (!vis[i]) {
//                dfs(i);
//            }
//        }
//        if (!valid) {
//            return {};
//        }
//        // 如果没有环，那么就有拓扑排序
//        // 下标 0 为栈底，需要将数组反序输出
//        reverse(ans.begin(), ans.end());
//        return ans;
//    }
//};

//2115. 从给定原材料中找到所有可以做出的菜

//你有 n 道不同菜的信息。给你一个字符串数组 recipes 和一个二维字符串数组 ingredients 。第 i 道菜的名字为 recipes[i] ，如果你有它 所有 的原材料 ingredients[i] ，那么你可以 做出 这道菜。
//一份食谱也可以是 其它 食谱的原料，也就是说 ingredients[i] 可能包含 recipes 中另一个字符串。
//同时给你一个字符串数组 supplies ，它包含你初始时拥有的所有原材料，每一种原材料你都有无限多。
//请你返回你可以做出的所有菜。你可以以 任意顺序 返回它们。
//注意两道菜在它们的原材料中可能互相包含。

//class Solution {
//public:
//    vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies) {
//        unordered_map<string, vector<string>> table;
//        unordered_map<string, int> indegree;
//        int n = recipes.size();
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < ingredients[i].size(); j++) {
//                table[ingredients[i][j]].emplace_back(recipes[i]); // 原料用于做什么
//                indegree[recipes[i]]++; // 需要的原料量
//            }
//        }
//        queue<string> q;
//        for (auto& sup : supplies) {
//            q.emplace(sup);
//        }
//        vector<string> ans;
//        while (!q.empty()) {
//            string tp = q.front();
//            q.pop();
//            for (auto& nxt : table[tp]) {
//                if (--indegree[nxt] == 0) {
//                    q.emplace(nxt);
//                    ans.emplace_back(nxt);
//                }
//            }
//        }
//        return ans;
//    }
//};

//2392. 给定条件下构造矩阵

//给你一个 正 整数 k ，同时给你：
//一个大小为 n 的二维整数数组 rowConditions ，其中 rowConditions[i] = [abovei, belowi] 和
//一个大小为 m 的二维整数数组 colConditions ，其中 colConditions[i] = [lefti, righti] 。
//两个数组里的整数都是 1 到 k 之间的数字。
//你需要构造一个 k x k 的矩阵，1 到 k 每个数字需要 恰好出现一次 。剩余的数字都是 0 。
//矩阵还需要满足以下条件：
//对于所有 0 到 n - 1 之间的下标 i ，数字 abovei 所在的 行 必须在数字 belowi 所在行的上面。
//对于所有 0 到 m - 1 之间的下标 i ，数字 lefti 所在的 列 必须在数字 righti 所在列的左边。
//返回满足上述要求的 任意 矩阵。如果不存在答案，返回一个空的矩阵。

//class Solution {
//    vector<int> topo_sort(int k, vector<vector<int>>& edges) {
//        vector<vector<int>> g(k);
//        vector<int> in_deg(k);
//        for (auto& e : edges) {
//            int x = e[0] - 1, y = e[1] - 1; // 顶点编号从 0 开始
//            g[x].emplace_back(y);
//            ++in_deg[y];
//        }
//
//        vector<int> order;
//        queue<int> q;
//        for (int i = 0; i < k; ++i) {
//            if (in_deg[i] == 0) {
//                q.emplace(i);
//            }
//        }
//        while (!q.empty()) {
//            int x = q.front();
//            q.pop();
//            order.emplace_back(x);
//            for (int y : g[x]) {
//                if (--in_deg[y] == 0) {
//                    q.emplace(y);
//                }
//            }
//        }
//        return order;
//    }
//
//public:
//    vector<vector<int>> buildMatrix(int k, vector<vector<int>>& rowConditions, vector<vector<int>>& colConditions) {
//        auto row = topo_sort(k, rowConditions), col = topo_sort(k, colConditions);
//        if (row.size() < k || col.size() < k)
//            return {};
//        vector<int> pos(k);
//        for (int i = 0; i < k; ++i) {
//            pos[col[i]] = i;
//        }
//        vector<vector<int>> ans(k, vector<int>(k));
//        for (int i = 0; i < k; ++i) {
//            ans[i][pos[row[i]]] = row[i] + 1;
//        }
//        return ans;
//    }
//};

//1591. 奇怪的打印机 II

//给你一个奇怪的打印机，它有如下两个特殊的打印规则：
//每一次操作时，打印机会用同一种颜色打印一个矩形的形状，每次打印会覆盖矩形对应格子里原本的颜色。
//一旦矩形根据上面的规则使用了一种颜色，那么 相同的颜色不能再被使用 。
//给你一个初始没有颜色的 m x n 的矩形 targetGrid ，其中 targetGrid[row][col] 是位置(row, col) 的颜色。
//如果你能按照上述规则打印出矩形 targetGrid ，请你返回 true ，否则返回 false 。

//class Solution {
//private:
//    static constexpr int COLOR = 61;
//
//public:
//    bool isPrintable(vector<vector<int>>& targetGrid) {
//        int m = targetGrid.size();
//        int n = targetGrid[0].size();
//
//        vector<int> up(COLOR, INT_MAX), down(COLOR), left(COLOR, INT_MAX), right(COLOR);
//        unordered_set<int> occur;
//        for (int i = 0; i < m; ++i) {
//            for (int j = 0; j < n; ++j) {
//                int color = targetGrid[i][j];
//                occur.insert(color);
//                up[color] = min(up[color], i);
//                down[color] = max(down[color], i);
//                left[color] = min(left[color], j);
//                right[color] = max(right[color], j);
//            }
//        }
//
//        vector<vector<int>> g(COLOR, vector<int>(COLOR));
//        vector<int> indeg(COLOR);
//        int nodes = occur.size();
//        for (int outside : occur) {
//            for (int i = up[outside]; i <= down[outside]; ++i) {
//                for (int j = left[outside]; j <= right[outside]; ++j) {
//                    int color = targetGrid[i][j];
//                    if (outside != color && !g[outside][color]) {
//                        g[outside][color] = 1;
//                        ++indeg[color];
//                    }
//                }
//            }
//        }
//
//        queue<int> q;
//        for (int color : occur) {
//            if (!indeg[color]) {
//                q.push(color);
//            }
//        }
//        while (!q.empty()) {
//            int u = q.front();
//            q.pop();
//            --nodes;
//            for (int v = 1; v < COLOR; ++v) {
//                if (g[u][v]) {
//                    --indeg[v];
//                    if (!indeg[v]) {
//                        q.push(v);
//                    }
//                }
//            }
//        }
//
//        return !nodes;
//    }
//};

//1203. 项目管理

//有 n 个项目，每个项目或者不属于任何小组，或者属于 m 个小组之一。group[i] 表示第 i 个项目所属的小组，如果第 i 个项目不属于任何小组，则 group[i] 等于 - 1。
//项目和小组都是从零开始编号的。可能存在小组不负责任何项目，即没有任何项目属于这个小组。
//请你帮忙按要求安排这些项目的进度，并返回排序后的项目列表：
//同一小组的项目，排序后在列表中彼此相邻。
//项目之间存在一定的依赖关系，我们用一个列表 beforeItems 来表示，其中 beforeItems[i] 表示在进行第 i 个项目前（位于第 i 个项目左侧）应该完成的所有项目。
//如果存在多个解决方案，只需要返回其中任意一个即可。如果没有合适的解决方案，就请返回一个 空列表 。

//class Solution {
//public:
//    vector<int> topsort(vector<int>& deg, vector<vector<int>>& graph, vector<int>& items) {
//        queue<int> Q;
//        for (auto& item : items) {
//            if (deg[item] == 0) {
//                Q.emplace(item);
//            }
//        }
//        vector<int> res;
//        while (!Q.empty()) {
//            int u = Q.front();
//            Q.pop();
//            res.emplace_back(u);
//            for (auto& v : graph[u]) {
//                if (--deg[v] == 0) {
//                    Q.emplace(v);
//                }
//            }
//        }
//        return res.size() == items.size() ? res : vector<int>{};
//    }
//
//    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
//        vector<vector<int>> groupItem(n + m);
//
//        // 组间和组内依赖图
//        vector<vector<int>> groupGraph(n + m);
//        vector<vector<int>> itemGraph(n);
//
//        // 组间和组内入度数组
//        vector<int> groupDegree(n + m, 0);
//        vector<int> itemDegree(n, 0);
//
//        vector<int> id;
//        for (int i = 0; i < n + m; ++i) {
//            id.emplace_back(i);
//        }
//
//        int leftId = m;
//        // 给未分配的 item 分配一个 groupId
//        for (int i = 0; i < n; ++i) {
//            if (group[i] == -1) {
//                group[i] = leftId;
//                leftId += 1;
//            }
//            groupItem[group[i]].emplace_back(i);
//        }
//        // 依赖关系建图
//        for (int i = 0; i < n; ++i) {
//            int curGroupId = group[i];
//            for (auto& item : beforeItems[i]) {
//                int beforeGroupId = group[item];
//                if (beforeGroupId == curGroupId) {
//                    itemDegree[i] += 1;
//                    itemGraph[item].emplace_back(i);
//                }
//                else {
//                    groupDegree[curGroupId] += 1;
//                    groupGraph[beforeGroupId].emplace_back(curGroupId);
//                }
//            }
//        }
//
//        // 组间拓扑关系排序
//        vector<int> groupTopsort = topsort(groupDegree, groupGraph, id);
//        if (groupTopsort.size() == 0) {
//            return {};
//        }
//        vector<int> ans;
//        // 组内拓扑关系排序
//        for (auto& curGroupId : groupTopsort) {
//            int size = groupItem[curGroupId].size();
//            if (size == 0) {
//                continue;
//            }
//            vector<int> res = topsort(itemDegree, itemGraph, groupItem[curGroupId]);
//            if (res.size() == 0) {
//                return vector<int>{};
//            }
//            for (auto& item : res) {
//                ans.emplace_back(item);
//            }
//        }
//        return ans;
//    }
//};

//2603. 收集树中金币

//给你一个 n 个节点的无向无根树，节点编号从 0 到 n - 1 。给你整数 n 和一个长度为 n - 1 的二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间有一条边。
//再给你一个长度为 n 的数组 coins ，其中 coins[i] 可能为 0 也可能为 1 ，1 表示节点 i 处有一个金币。
//一开始，你需要选择树中任意一个节点出发。你可以执行下述操作任意次：
//收集距离当前节点距离为 2 以内的所有金币，或者
//移动到树中一个相邻节点。
//你需要收集树中所有的金币，并且回到出发节点，请你返回最少经过的边数。
//如果你多次经过一条边，每一次经过都会给答案加一。

//class Solution {
//public:
//    int collectTheCoins(vector<int>& coins, vector<vector<int>>& edges) {
//        int n = coins.size();
//        vector<vector<int>> g(n);
//        vector<int> deg(n);
//        for (auto& e : edges) {
//            int x = e[0], y = e[1];
//            g[x].emplace_back(y);
//            g[y].emplace_back(x); // 建图
//            deg[x]++;
//            deg[y]++; // 统计每个节点的邻居个数
//        }
//
//        int left_edges = n - 1; // 剩余边数
//        vector<int> q;
//        for (int i = 0; i < n; i++) {
//            if (deg[i] == 1 && coins[i] == 0) { // 没有金币的叶子
//                q.emplace_back(i);
//            }
//        }
//        while (!q.empty()) {
//            left_edges--; // 删除节点 x
//            int x = q.back(); q.pop_back();
//            for (int y : g[x]) {
//                if (--deg[y] == 1 && coins[y] == 0) { // 没有金币的叶子
//                    q.emplace_back(y);
//                }
//            }
//        }
//
//        for (int i = 0; i < n; i++) {
//            if (deg[i] == 1 && coins[i]) { // 有金币的叶子
//                q.emplace_back(i);
//            }
//        }
//        left_edges -= q.size(); // 删除所有叶子
//        for (int x : q) { // 遍历所有叶子
//            for (int y : g[x]) {
//                if (--deg[y] == 1) { // y 现在是叶子了
//                    left_edges--; // 删除 y
//                }
//            }
//        }
//        return max(left_edges * 2, 0);
//    }
//};

//LCR 114. 火星词典

//现有一种使用英语字母的外星文语言，这门语言的字母顺序与英语顺序不同。
//给定一个字符串列表 words ，作为这门语言的词典，words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
//请你根据该词典还原出此语言中已知的字母顺序，并 按字母递增顺序 排列。若不存在合法字母顺序，返回 "" 。若存在多种可能的合法字母顺序，返回其中 任意一种 顺序即可。
//字符串 s 字典顺序小于 字符串 t 有两种情况：
//在第一个不同字母处，如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前，那么 s 的字典顺序小于 t 。
//如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 时，s 的字典顺序也小于 t 。

//class Solution {
//public:
//    const int VISITING = 1, VISITED = 2;
//    unordered_map<char, vector<char>> edges;
//    unordered_map<char, int> states;
//    bool valid = true;
//    string order;
//    int index;
//
//    string alienOrder(vector<string>& words) {
//        int length = words.size();
//        for (string& word : words) {
//            int wordLength = word.size();
//            for (int j = 0; j < wordLength; j++) {
//                char c = word[j];
//                if (!edges.count(c)) {
//                    edges[c] = vector<char>();
//                }
//            }
//        }
//        for (int i = 1; i < length && valid; i++) {
//            addEdge(words[i - 1], words[i]);
//        }
//        order = string(edges.size(), ' ');
//        index = edges.size() - 1;
//        for (auto [u, _] : edges) {
//            if (!states.count(u)) {
//                dfs(u);
//            }
//        }
//        if (!valid) {
//            return "";
//        }
//        return order;
//    }
//
//    void addEdge(string before, string after) {
//        int length1 = before.size(), length2 = after.size();
//        int length = min(length1, length2);
//        int index = 0;
//        while (index < length) {
//            char c1 = before[index], c2 = after[index];
//            if (c1 != c2) {
//                edges[c1].emplace_back(c2);
//                break;
//            }
//            index++;
//        }
//        if (index == length && length1 > length2) {
//            valid = false;
//        }
//    }
//
//    void dfs(char u) {
//        states[u] = VISITING;
//        for (char v : edges[u]) {
//            if (!states.count(v)) {
//                dfs(v);
//                if (!valid) {
//                    return;
//                }
//            }
//            else if (states[v] == VISITING) {
//                valid = false;
//                return;
//            }
//        }
//        states[u] = VISITED;
//        order[index] = u;
//        index--;
//    }
//};

//310. 最小高度树

//树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，任何一个没有简单环路的连通图都是一棵树。
//给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。
//给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。
//可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。
//请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
//树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。

//class Solution {
//public:
//    int findLongestNode(int u, vector<int>& parent, vector<vector<int>>& adj) {
//        int n = adj.size();
//        queue<int> qu;
//        vector<int8_t> visit(n);
//        qu.emplace(u);
//        visit[u] = true;
//        int node = -1;
//
//        while (!qu.empty()) {
//            int curr = qu.front();
//            qu.pop();
//            node = curr;
//            for (auto& v : adj[curr]) {
//                if (!visit[v]) {
//                    visit[v] = true;
//                    parent[v] = curr;
//                    qu.emplace(v);
//                }
//            }
//        }
//        return node;
//    }
//
//    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
//        if (n == 1) {
//            return { 0 };
//        }
//        vector<vector<int>> adj(n);
//        for (auto& edge : edges) {
//            adj[edge[0]].emplace_back(edge[1]);
//            adj[edge[1]].emplace_back(edge[0]);
//        }
//
//        vector<int> parent(n, -1);
//        // 找到与节点 0 最远的节点 x
//        int x = findLongestNode(0, parent, adj);
//        // 找到与节点 x 最远的节点 y
//        int y = findLongestNode(x, parent, adj);
//        // 求出节点 x 到节点 y 的路径
//        vector<int> path;
//        parent[x] = -1;
//        while (y != -1) {
//            path.emplace_back(y);
//            y = parent[y];
//        }
//        int m = path.size();
//        if (m % 2 == 0) {
//            return { path[m / 2 - 1], path[m / 2] };
//        }
//        else {
//            return { path[m / 2] };
//        }
//    }
//};

//851. 喧闹和富有

//有一组 n 个人作为实验对象，从 0 到 n - 1 编号，其中每个人都有不同数目的钱，以及不同程度的安静值（quietness）。为了方便起见，我们将编号为 x 的人简称为 "person x "。
//给你一个数组 richer ，其中 richer[i] = [ai, bi] 表示 person ai 比 person bi 更有钱。另给你一个整数数组 quiet ，其中 quiet[i] 是 person i 的安静值。
//richer 中所给出的数据 逻辑自洽（也就是说，在 person x 比 person y 更有钱的同时，不会出现 person y 比 person x 更有钱的情况 ）。
//现在，返回一个整数数组 answer 作为答案，其中 answer[x] = y 的前提是，在所有拥有的钱肯定不少于 person x 的人中，person y 是最不安静的人（也就是安静值 quiet[y] 最小的人）。

//class Solution {
//public:
//    vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) {
//        int n = quiet.size();
//        vector<vector<int>> g(n);
//        for (auto& r : richer) {
//            g[r[1]].emplace_back(r[0]); // 建图
//        }
//
//        vector<int> ans(n, -1);
//        auto dfs = [&](this auto&& dfs, int x) -> void {
//            if (ans[x] != -1) {
//                return;
//            }
//            ans[x] = x;
//            for (int y : g[x]) {
//                dfs(y);
//                if (quiet[ans[y]] < quiet[ans[x]]) {
//                    ans[x] = ans[y];
//                }
//            }
//            };
//        for (int i = 0; i < n; ++i) {
//            dfs(i);
//        }
//        return ans;
//    }
//};

//2050. 并行课程 III

//给你一个整数 n ，表示有 n 节课，课程编号从 1 到 n 。同时给你一个二维整数数组 relations ，其中 relations[j] = [prevCoursej, nextCoursej] ，表示课程 prevCoursej 必须在课程 nextCoursej 之前 完成（先修课的关系）。
//同时给你一个下标从 0 开始的整数数组 time ，其中 time[i] 表示完成第(i + 1) 门课程需要花费的 月份 数。
//请你根据以下规则算出完成所有课程所需要的 最少 月份数：
//如果一门课的所有先修课都已经完成，你可以在 任意 时间开始这门课程。
//你可以 同时 上 任意门课程 。
//请你返回完成所有课程所需要的 最少 月份数。
//注意：测试数据保证一定可以完成所有课程（也就是先修课的关系构成一个有向无环图）。

//class Solution {
//public:
//    int minimumTime(int n, vector<vector<int>>& relations, vector<int>& time) {
//        vector<vector<int>> g(n);
//        vector<int> deg(n);
//        for (auto& r : relations) {
//            int x = r[0] - 1, y = r[1] - 1;
//            g[x].push_back(y); // 建图
//            deg[y]++; // y 的先修课的个数
//        }
//
//        queue<int> q;
//        for (int i = 0; i < n; i++)
//            if (deg[i] == 0) { // 没有先修课
//                q.emplace(i);
//            }
//        vector<int> f(n);
//        while (!q.empty()) {
//            int x = q.front();
//            q.pop();
//            f[x] += time[x];
//            for (int y : g[x]) {
//                f[y] = max(f[y], f[x]); // 更新 f[y] 的所有先修课程耗时的最大值
//                if (--deg[y] == 0) // y 的先修课已上完
//                    q.emplace(y);
//            }
//        }
//        return *max_element(f.begin(), f.end());
//    }
//};

//3620. 恢复网络路径

//给你一个包含 n 个节点（编号从 0 到 n - 1）的有向无环图。图由长度为 m 的二维数组 edges 表示，
//其中 edges[i] = [ui, vi, costi] 表示从节点 ui 到节点 vi 的单向通信，恢复成本为 costi。
//一些节点可能处于离线状态。给定一个布尔数组 online，其中 online[i] = true 表示节点 i 在线。节点 0 和 n - 1 始终在线。
//从 0 到 n - 1 的路径如果满足以下条件，那么它是 有效 的：
//路径上的所有中间节点都在线。
//路径上所有边的总恢复成本不超过 k。
//对于每条有效路径，其 分数 定义为该路径上的最小边成本。
//返回所有有效路径中的 最大 路径分数（即最大 最小 边成本）。如果没有有效路径，则返回 - 1。

//class Solution {
//public:
//    int findMaxPathScore(vector<vector<int>>& edges, vector<bool>& online, long long k) {
//        int n = online.size();
//        vector<vector<pair<int, int>>> g(n);
//        vector<int> deg(n);
//        int max_wt = -1;
//        for (auto& e : edges) {
//            int x = e[0], y = e[1], wt = e[2];
//            if (online[x] && online[y]) {
//                g[x].emplace_back(y, wt);
//                deg[y]++;
//                if (x == 0) {
//                    max_wt = max(max_wt, wt);
//                }
//            }
//        }
//
//        // 清理无法从 0 到达的边
//        queue<int> q;
//        for (int i = 1; i < n; i++) {
//            if (deg[i] == 0) {
//                q.emplace(i);
//            }
//        }
//        while (!q.empty()) {
//            int x = q.front();
//            q.pop();
//            for (auto& [y, _] : g[x]) {
//                if (--deg[y] == 0 && y) {
//                    q.emplace(y);
//                }
//            }
//        }
//
//        vector<long long> f(n);
//        auto check = [&](int lower) -> bool {
//            auto deg_copy = deg;
//            ranges::fill(f, LLONG_MAX / 2); // 除 2 防止加法溢出
//            f[0] = 0;
//
//            queue<int> q;
//            q.emplace(0);
//            while (!q.empty()) {
//                int x = q.front();
//                q.pop();
//                if (x == n - 1) {
//                    return f[x] <= k;
//                }
//                for (auto& [y, wt] : g[x]) {
//                    if (wt >= lower) {
//                        f[y] = min(f[y], f[x] + wt);
//                    }
//                    if (--deg_copy[y] == 0) {
//                        q.emplace(y);
//                    }
//                }
//            }
//            return false; // 无法到达 n-1
//            };
//
//        int left = -1, right = max_wt + 1;
//        while (left + 1 < right) {
//            int mid = left + (right - left) / 2;
//            (check(mid) ? left : right) = mid;
//        }
//        return left;
//    }
//};

//1857. 有向图中最大颜色值

//给你一个 有向图 ，它含有 n 个节点和 m 条边。节点编号从 0 到 n - 1 。
//给你一个字符串 colors ，其中 colors[i] 是小写英文字母，表示图中第 i 个节点的 颜色 （下标从 0 开始）。
//同时给你一个二维数组 edges ，其中 edges[j] = [aj, bj] 表示从节点 aj 到节点 bj 有一条 有向边 。
//图中一条有效 路径 是一个点序列 x1->x2->x3 -> ...->xk ，对于所有 1 <= i < k ，从 xi 到 xi + 1 在图中有一条有向边。路径的 颜色值 是路径中 出现次数最多 颜色的节点数目。
//请你返回给定图中有效路径里面的 最大颜色值 。如果图中含有环，请返回 - 1 。

//class Solution {
//public:
//    int largestPathValue(string colors, vector<vector<int>>& edges) {
//        int n = colors.size();
//        vector<vector<int>> g(n);
//        vector<int> deg(n);
//        for (auto& e : edges) {
//            int x = e[0], y = e[1];
//            if (x == y) { // 自环
//                return -1;
//            }
//            g[x].emplace_back(y);
//            deg[y]++;
//        }
//
//        vector<int> q;
//        for (int i = 0; i < n; i++) {
//            if (deg[i] == 0) {
//                q.emplace_back(i); // 入度为 0 的点入队
//            }
//        }
//
//        int ans = 0;
//        vector<array<int, 26>> f(n);
//        for (int i = 0; i < q.size(); i++) { // 注意 q.size() 会变大
//            int x = q[i]; // x 的所有转移来源都计算完毕，也都更新到 f[x] 中
//            int ch = colors[x] - 'a';
//            f[x][ch]++;
//            ans = max(ans, f[x][ch]);
//            for (int y : g[x]) {
//                for (int j = 0; j < 26; j++) {
//                    f[y][j] = max(f[y][j], f[x][j]); // 刷表法，更新邻居的最大值
//                }
//                if (--deg[y] == 0) {
//                    q.emplace_back(y);
//                }
//            }
//        }
//
//        return q.size() < n ? -1 : ans;
//    }
//};

//2359. 找到离给定两个节点最近的节点

//给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，每个节点 至多 有一条出边。
//有向图用大小为 n 下标从 0 开始的数组 edges 表示，表示节点 i 有一条有向边指向 edges[i] 。如果节点 i 没有出边，那么 edges[i] == -1 。
//同时给你两个节点 node1 和 node2 。
//请你返回一个从 node1 和 node2 都能到达节点的编号，使节点 node1 和节点 node2 到这个节点的距离 较大值最小化。如果有多个答案，请返回 最小 的节点编号。如果答案不存在，返回 - 1 。
//注意 edges 可能包含环。

//class Solution {
//public:
//    int closestMeetingNode(vector<int>& edges, int node1, int node2) {
//        int n = edges.size();
//        auto calc_dis = [&](int x) {
//            vector<int> dis(n, n); // 初始化成 n，表示无法到达或者尚未访问的节点
//            for (int d = 0; x >= 0 && dis[x] == n; x = edges[x]) {
//                dis[x] = d++;
//            }
//            return dis;
//            };
//
//        vector<int> dis1 = calc_dis(node1);
//        vector<int> dis2 = calc_dis(node2);
//
//        int min_dis = n, ans = -1;
//        for (int i = 0; i < n; i++) {
//            int d = max(dis1[i], dis2[i]);
//            if (d < min_dis) {
//                min_dis = d;
//                ans = i;
//            }
//        }
//        return ans;
//    }
//};

//2360. 图中的最长环

//给你一个 n 个节点的 有向图 ，节点编号为 0 到 n - 1 ，其中每个节点 至多 有一条出边。
//图用一个大小为 n 下标从 0 开始的数组 edges 表示，节点 i 到节点 edges[i] 之间有一条有向边。如果节点 i 没有出边，那么 edges[i] == -1 。
//请你返回图中的 最长 环，如果没有任何环，请返回 - 1 。
//一个环指的是起点和终点是 同一个 节点的路径。

//class Solution {
//public:
//    int longestCycle(vector<int>& edges) {
//        int n = edges.size();
//        int ans = -1;
//        int cur_time = 1; // 当前时间
//        vector<int> vis_time(n); // 首次访问 x 的时间
//        for (int i = 0; i < n; i++) {
//            int x = i;
//            int start_time = cur_time;
//            while (x != -1 && vis_time[x] == 0) { // 没有访问过 x
//                vis_time[x] = cur_time++;
//                x = edges[x];
//            }
//            if (x != -1 && vis_time[x] >= start_time) { // x 在本轮循环中访问了两次，说明 x 在环上
//                ans = max(ans, cur_time - vis_time[x]);
//            }
//        }
//        return ans;
//    }
//};

//684. 冗余连接

//树可以看成是一个连通且 无环 的 无向 图。
//给定一个图，该图从一棵 n 个节点(节点值 1～n) 的树中添加一条边后获得。添加的边的两个不同顶点编号在 1 到 n 中间，且这条附加的边不属于树中已存在的边。
//图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
//请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。

//class Solution {
//public:
//    int Find(vector<int>& parent, int index) {
//        if (parent[index] != index) {
//            parent[index] = Find(parent, parent[index]);
//        }
//        return parent[index];
//    }
//
//    void Union(vector<int>& parent, int index1, int index2) {
//        parent[Find(parent, index1)] = Find(parent, index2);
//    }
//
//    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
//        int n = edges.size();
//        vector<int> parent(n + 1);
//        for (int i = 1; i <= n; ++i) {
//            parent[i] = i;
//        }
//        for (auto& edge : edges) {
//            int node1 = edge[0], node2 = edge[1];
//            if (Find(parent, node1) != Find(parent, node2)) {
//                Union(parent, node1, node2);
//            }
//            else {
//                return edge;
//            }
//        }
//        return {};
//    }
//};

//685. 冗余连接 II

//在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。
//输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。
//结果图是一个以边组成的二维数组 edges 。 每个元素是一对[ui, vi]，用以表示 有向 图中连接顶点 ui 和顶点 vi 的边，其中 ui 是 vi 的一个父节点。
//返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。

//struct UnionFind {
//    vector <int> ancestor;
//
//    UnionFind(int n) {
//        ancestor.resize(n);
//        for (int i = 0; i < n; ++i) {
//            ancestor[i] = i;
//        }
//    }
//
//    int find(int index) {
//        return index == ancestor[index] ? index : ancestor[index] = find(ancestor[index]);
//    }
//
//    void merge(int u, int v) {
//        ancestor[find(u)] = find(v);
//    }
//};
//
//class Solution {
//public:
//    vector<int> findRedundantDirectedConnection(vector<vector<int>>& edges) {
//        int n = edges.size();
//        UnionFind uf = UnionFind(n + 1);
//        auto parent = vector<int>(n + 1);
//        for (int i = 1; i <= n; ++i) {
//            parent[i] = i;
//        }
//        int conflict = -1;
//        int cycle = -1;
//        for (int i = 0; i < n; ++i) {
//            auto edge = edges[i];
//            int node1 = edge[0], node2 = edge[1];
//            if (parent[node2] != node2) {
//                conflict = i;
//            }
//            else {
//                parent[node2] = node1;
//                if (uf.find(node1) == uf.find(node2)) {
//                    cycle = i;
//                }
//                else {
//                    uf.merge(node1, node2);
//                }
//            }
//        }
//        if (conflict < 0) {
//            auto redundant = vector<int>{ edges[cycle][0], edges[cycle][1] };
//            return redundant;
//        }
//        else {
//            auto conflictEdge = edges[conflict];
//            if (cycle >= 0) {
//                auto redundant = vector<int>{ parent[conflictEdge[1]], conflictEdge[1] };
//                return redundant;
//            }
//            else {
//                auto redundant = vector<int>{ conflictEdge[0], conflictEdge[1] };
//                return redundant;
//            }
//        }
//    }
//};

//2876. 有向图访问计数

//现有一个有向图，其中包含 n 个节点，节点编号从 0 到 n - 1 。此外，该图还包含了 n 条有向边。
//给你一个下标从 0 开始的数组 edges ，其中 edges[i] 表示存在一条从节点 i 到节点 edges[i] 的边。
//想象在图上发生以下过程：
//你从节点 x 开始，通过边访问其他节点，直到你在 此过程 中再次访问到之前已经访问过的节点。
//返回数组 answer 作为答案，其中 answer[i] 表示如果从节点 i 开始执行该过程，你可以访问到的不同节点数。

//class Solution {
//public:
//    vector<int> countVisitedNodes(vector<int>& g) {
//        int n = g.size();
//        vector<vector<int>> rg(n); // 反图
//        vector<int> deg(n);
//        for (int x = 0; x < n; x++) {
//            int y = g[x];
//            rg[y].push_back(x);
//            deg[y]++;
//        }
//
//        // 拓扑排序后，deg 值为 1 的点必定在基环上，为 0 的点必定在树枝上
//        queue<int> q;
//        for (int i = 0; i < n; i++) {
//            if (deg[i] == 0) {
//                q.push(i);
//            }
//        }
//        while (!q.empty()) {
//            int x = q.front();
//            q.pop();
//            int y = g[x];
//            if (--deg[y] == 0) {
//                q.push(y);
//            }
//        }
//
//        vector<int> ans(n, 0);
//        function<void(int, int)> rdfs = [&](int x, int depth) {
//            ans[x] = depth;
//            for (int y : rg[x]) {
//                if (deg[y] == 0) { // 树枝上的点在拓扑排序后，入度均为 0
//                    rdfs(y, depth + 1);
//                }
//            }
//            };
//        for (int i = 0; i < n; i++) {
//            if (deg[i] <= 0) {
//                continue;
//            }
//            vector<int> ring;
//            for (int x = i;; x = g[x]) {
//                deg[x] = -1; // 将基环上的点的入度标记为 -1，避免重复访问
//                ring.push_back(x); // 收集在基环上的点
//                if (g[x] == i) {
//                    break;
//                }
//            }
//            for (int x : ring) {
//                rdfs(x, ring.size()); // 为方便计算，以 ring.size() 作为初始深度
//            }
//        }
//        return ans;
//    }
//};

//2127. 参加会议的最多员工数

//一个公司准备组织一场会议，邀请名单上有 n 位员工。公司准备了一张 圆形 的桌子，可以坐下 任意数目 的员工。
//员工编号为 0 到 n - 1 。每位员工都有一位 喜欢 的员工，每位员工 当且仅当 他被安排在喜欢员工的旁边，他才会参加会议。每位员工喜欢的员工 不会 是他自己。
//给你一个下标从 0 开始的整数数组 favorite ，其中 favorite[i] 表示第 i 位员工喜欢的员工。请你返回参加会议的 最多员工数目 。

//class Solution {
//public:
//    int maximumInvitations(vector<int>& favorite) {
//        int n = favorite.size();
//        vector<int> deg(n);
//        for (int f : favorite) {
//            deg[f]++; // 统计基环树每个节点的入度
//        }
//
//        vector<int> max_depth(n, 1);
//        queue<int> q;
//        for (int i = 0; i < n; i++) {
//            if (deg[i] == 0) {
//                q.emplace(i);
//            }
//        }
//        while (!q.empty()) { // 拓扑排序，剪掉图上所有树枝
//            int x = q.front();
//            q.pop();
//            int y = favorite[x]; // x 只有一条出边
//            max_depth[y] = max_depth[x] + 1;
//            if (--deg[y] == 0) {
//                q.emplace(y);
//            }
//        }
//
//        int max_ring_size = 0, sum_chain_size = 0;
//        for (int i = 0; i < n; i++) {
//            if (deg[i] == 0) continue;
//
//            // 遍历基环上的点
//            deg[i] = 0; // 将基环上的点的入度标记为 0，避免重复访问
//            int ring_size = 1; // 基环长度
//            for (int x = favorite[i]; x != i; x = favorite[x]) {
//                deg[x] = 0; // 将基环上的点的入度标记为 0，避免重复访问
//                ring_size++;
//            }
//
//            if (ring_size == 2) { // 基环长度为 2
//                sum_chain_size += max_depth[i] + max_depth[favorite[i]]; // 累加两条最长链的长度
//            }
//            else {
//                max_ring_size = max(max_ring_size, ring_size); // 取所有基环长度的最大值
//            }
//        }
//        return max(max_ring_size, sum_chain_size);
//    }
//};

//2836. 在传球游戏中最大化函数值

//给你一个长度为 n 下标从 0 开始的整数数组 receiver 和一个整数 k 。
//总共有 n 名玩家，玩家 编号 互不相同，且为[0, n - 1] 中的整数。这些玩家玩一个传球游戏，receiver[i] 表示编号为 i 的玩家会传球给编号为 receiver[i] 的玩家。
//玩家可以传球给自己，也就是说 receiver[i] 可能等于 i 。
//你需要从 n 名玩家中选择一名玩家作为游戏开始时唯一手中有球的玩家，球会被传 恰好 k 次。
//如果选择编号为 x 的玩家作为开始玩家，定义函数 f(x) 表示从编号为 x 的玩家开始，k 次传球内所有接触过球玩家的编号之 和 ，如果有玩家多次触球，则 累加多次 。
//换句话说， f(x) = x + receiver[x] + receiver[receiver[x]] + ... + receiver(k)[x] 。
//你的任务时选择开始玩家 x ，目的是 最大化 f(x) 。
//请你返回函数的 最大值 。
//注意：receiver 可能含有重复元素。

//class Solution {
//public:
//    long long getMaxFunctionValue(vector<int>& receiver, long long K) {
//        int n = receiver.size();
//        int m = 64 - countl_zero(static_cast<uint64_t>(K));
//        vector<vector<pair<int, long long>>> pa(m, vector<pair<int, long long>>(n));
//        for (int i = 0; i < n; i++)
//            pa[0][i] = { receiver[i], receiver[i] };
//        for (int i = 0; i < m - 1; i++) {
//            for (int x = 0; x < n; x++) {
//                auto [p, s] = pa[i][x];
//                auto [pp, ss] = pa[i][p];
//                pa[i + 1][x] = { pp, s + ss }; // 合并节点值之和
//            }
//        }
//
//        long long ans = 0;
//        for (int i = 0; i < n; i++) {
//            long long sum = i;
//            int x = i;
//            for (long long k = K; k; k &= k - 1) {
//                auto [p, s] = pa[__builtin_ctzll(k)][x]; // uint问题最快解决法
//                sum += s;
//                x = p;
//            }
//            ans = max(ans, sum);
//        }
//        return ans;
//    }
//};